Exercises for Genetic Algorithm for TSP

Ex 1. Fitness evaluation
- Ex 1.1 Tour length
- Ex 1.2 Fitness ratio
Ex 2. Selection
- Roulette wheel
Ex 3. Crossover
Ex 4. Mutation

Exercise 1.1 - Tour Length: Let's get the total traveling distance.
<div id='tr1-1-output'></div> <script> var CITIES = []; CITIES[0] = {}; CITIES[0].x = 0; CITIES[0].y = 50; CITIES[1] = {}; CITIES[1].x = 10; CITIES[1].y = 35; CITIES[2] = {}; CITIES[2].x = 40; CITIES[2].y = 15; CITIES[3] = {}; CITIES[3].x = 30; CITIES[3].y = 20; function get_tour_length(tour, CITIES) { var sum = 0; ??? // Use Eucledean distance. You may use Math.sqrt() and Math.pow() return sum; } var tour = [1, 0, 3, 2]; // tour: [1, 0, 3, 2] var tour_length = get_tour_length(tour, CITIES); $('#tr1-1-output').html(tour_length); </script>

Exercise 1.2 - Fitness Evaluation: Let's compute the fitness values. This exercise should be done after Exercise 1.
<div id='tr1-2-output'></div> <script> function get_fitness_ratios(tour_lengths, CITIES) // Fitness values: Idea 3 { var total = 0; var fitnesses = []; var fitness_ratios = []; ??? return fitness_ratios; } var tours = []; tours[0] = [1, 0, 3, 2]; // tour0: [1, 0, 3, 2] tours[1] = [0, 2, 1, 3]; // tour1: [0, 2, 1, 3] tours[2] = [1, 3, 2, 0]; // tour2: [1, 3, 2, 0] tours[3] = [3, 0, 1, 2]; // tour3: [3, 0, 1, 2] var tour_lengths = []; tour_lengths[0] = get_tour_length(tours[0], CITIES); tour_lengths[1] = get_tour_length(tours[1], CITIES); tour_lengths[2] = get_tour_length(tours[2], CITIES); tour_lengths[3] = get_tour_length(tours[3], CITIES); var fitness_ratios = get_fitness_ratios(tour_lengths, CITIES); $('#tr1-2-output').html(fitness_ratios[0] + ", " + fitness_ratios[1] + ", " + fitness_ratios[2] + ", " + fitness_ratios[3]); </script>

Exercise 2 - Selection: Let's select a tour using the Roulette wheel selection. This exercise should be done after Exercise 1.
<div id='tr2-output'></div> <script> function make_roulette_wheel(fitness_ratios) { var roulette_wheel = []; ??? return roulette_wheel; } function select_tour_with_RouletteWheel(wheel) { var r; r = Math.random(); // [0, 1) ??? } var roulette_wheel = make_roulette_wheel(fitness_ratios); var selected_tour_no_0, selected_tour_no_1; selected_tour_no_0 = select_tour_with_RouletteWheel(roulette_wheel); selected_tour_no_1 = select_tour_with_RouletteWheel(roulette_wheel); $('#tr2-output').html(selected_tour_no_0 + ", " + selected_tour_no_1); </script>

Exercise 3 - Crossover: Let's apply crossover. This exercise should be done after Exercise 2.
<div id='tr3-output'></div> <script> function do_crossover(parents) // Idea 1 with the middle point { var offsprings = []; // two individuals offsprings[0] = []; offsprings[1] = []; var cross_point = ???; // the middle point for (var i = 0; i < cross_point; i++) offsprings[0][i] = parents[0][i]; for (var i = cross_point; i < parents[0].length; i++) offsprings[0][i] = find_not_used_city(offsprings[0], i, parents[1]); ??? return offsprings; } // Find the city, that is not used in offspring[], from the position x to the end, and from 0 to x-1 function find_not_used_city(offspring, x, parent) // Note that offspring[0] ... offspring[x-1] are already decided. { var i, j, k; for (i = x; i < parent.length; i++) // check from x to the end if (!is_city_used(offspring, x, parent[i])) return parent[i]; for (i = 0; i < x-1; i++) // check from 0 to x-1 if (!is_city_used(offspring, x, parent[i])) return parent[i]; } // Check if the city is in offspring[] among the positions from 0 to x-1 function is_city_used(offspring, x, city) // Note that offspring[0] ... offspring[x-1] are already decided. { for (var i = 0; i < x; i++) if (offspring[i] == city) return true; return false; } var parents = []; parents[0] = tours[selected_tour_no_0]; parents[1] = tours[selected_tour_no_1]; var offsprings = []; offsprings = do_crossover(parents); $('#tr3-output').html(offsprings[0].toString() + ", " + offsprings[1].toString()); </script>

Exercise 4 - Mutation: Let's mutate the new offsprings. This exercise should be done after Exercise 3.
<div id='tr4-output'></div> <script> function mutate(offspring) // Idea 1 { var city_no_0, city_no_1; // select two different cities city_no_0 = Math.floor(Math.random() * offspring.length); while(true) { city_no_1 = Math.floor(Math.random() * offspring.length); if (city_no_0 != city_no_1) break; } // make sure city numbers in order if (city_no_0 > city_no_1) { var tmp = city_no_0; city_no_0 = city_no_1; city_no_1 = tmp; } // apply mutation ??? } var RATE_MUTATION = 0.3; // Just for exercise // apply mutation to two offsprings separately with RATE_MUTATION ??? $('#tr4-output').html(offsprings[0].toString() + ", " + offsprings[1].toString()); </script>